package com.cqs.leetcode.backtrack;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author lixqw
 * @date 2020/9/8
 */
public class CombinationSumIII {

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> list = new ArrayList<>();
        if (k == 0) return list;
        combination(k, n, new ArrayList<>(), list);
        return list;
    }

    private void combination(int k, int target, List<Integer> tmp, List<List<Integer>> list) {
        if (k == 1) {
            if (target >= 1 && target <= 9 && !tmp.contains(target)) {
                //去重[1,2,6] --[1,6,2]
                if (tmp.size() > 0 && target < tmp.get(tmp.size() - 1)) return;
                List<Integer> l = new ArrayList<>(tmp);
                l.add(target);
                list.add(l);
            }
            return;
        }

        for (int i = 1; i < 10; i++) {
            if (tmp.contains(i)) continue;
            //去重[1,2,6] --[6,1,2]
            if (tmp.size() > 0 && i < tmp.get(tmp.size() - 1)) continue;
            tmp.add(i);
            combination(k - 1, target - i, tmp, list);
            tmp.remove(tmp.size() - 1);
        }
    }

    public static void main(String[] args) {
        Map<Integer, Integer> tests = new HashMap<>();
        CombinationSumIII c = new CombinationSumIII();
        tests.put(3, 9);
        tests.forEach((k, n) -> {
            List<List<Integer>> lists = c.combinationSum3(k, n);
            System.out.println(lists);
        });
    }
}
